package DoExercise.HSP_ZCY.A009_图结构.A001_并查集;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 *
 * 拓扑排序：在一个有向图中，对所有的节点进行排序，要求没有一个节点指向它前面的节点。
 * 1 先统计所有节点的入度，对于入度为0的节点就可以分离出来，然后把这个节点指向的节点的入度减一。
 * 2 一直做改操作，直到所有的节点都被分离出来。
 * 3 如果最后不存在入度为0的节点，那就说明有环，不存在拓扑排序，也就是很多题目的无解的情况。
 */
public class Code03_拓扑排序
{
    /**
     * 确定拓扑排序
     *
     * @param graph
     * @return
     */
    public static List<Node> sortedTopology(Graph graph)
    {
        HashMap<Node, Integer> inMap = new HashMap<>();//key：某一个node，value：剩余的入度，入度会逐渐减少
        Queue<Node> zeroInQueue = new LinkedList<>();//入度为0的点，才能进这个队列
        for (Node node : graph.nodes.values())
        {
            inMap.put(node, node.in);//初始化剩余入度
            if (node.in == 0)
            {
                zeroInQueue.add(node);//入度为0的点
            }
        }

        List<Node> result = new ArrayList<>();
        //逐个处理入度为0的点
        while (!zeroInQueue.isEmpty())
        {
            Node cur = zeroInQueue.poll();
            result.add(cur);
            for (Node next : cur.nexts)
            {
                inMap.put(next, inMap.get(next) - 1);//把当前点所有邻居点的入度-1，消除当前点的影响
                if (inMap.get(next) == 0)
                {
                    zeroInQueue.add(next);
                }
            }
        }
        return result;
    }
}
